from typing import List


class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        size = len(satisfaction)

        # 考虑菜品顺序
        ans = 0
        for i, s in enumerate(satisfaction):
            ans += (i + 1) * s

        # 计算后缀和
        suffix = [0] * (size + 1)
        for i in range(size - 1, -1, -1):
            suffix[i] = suffix[i + 1] + satisfaction[i]

        # 考虑删除一些菜
        for i, s in enumerate(satisfaction):
            if s < 0:
                v1, v2 = suffix[i + 1], s
                if v1 + v2 < 0:
                    ans -= (v1 + v2)
        return ans


if __name__ == "__main__":
    print(Solution().maxSatisfaction(satisfaction=[-1, -8, 0, 5, -9]))  # 14
    print(Solution().maxSatisfaction(satisfaction=[4, 3, 2]))  # 20
    print(Solution().maxSatisfaction(satisfaction=[-1, -4, -5]))  # 0
    print(Solution().maxSatisfaction(satisfaction=[-2, 5, -1, 0, 3, -3]))  # 35
